﻿#include"sort.h"
void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


//void _mesort(int* arr, int left, int right, int* tmp)
//{
//	//分离
//	//{
//	//递归结束条件
//	if (left >= right)
//	{
//		return;
//	}
//
//	//找中间下标
//	int mid = (left+right) / 2;
//	// [left,mid]  [mid+1,right]
//	// 递归地对左区间进行排序
//	_mesort(arr, left, mid, tmp);
//	// 递归地对右区间进行排序
//	_mesort(arr, mid + 1, right, tmp);
//	//}
//
//
//
//	//合并
//	// [left,mid]  [mid+1,right]
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//
//	int index = begin1;//midex下标用来存放到tmp数组中
//	
//	// 依次比较两个begin1和begin2区间，将较小的元素放入tmp数组
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (arr[begin1] < arr[begin2])
//		{
//			tmp[index++] = arr[begin1++];
//		}
//		else
//		{
//			tmp[index++] = arr[begin2++];
//		}
//
//	}
//	//begin1和begin2，会有一个越界，需要处理
//	while (begin1 <= end1)
//	{
//		tmp[index++] = arr[begin1++];
//	}
//	while (begin2 <= end2)
//	{
//		tmp[index++] = arr[begin2++];
//	}
//	
//	//把tmp数组的数值拷贝到arr数组
//	for (int i = left; i <= right; i++)
//	{
//		arr[i] = tmp[i];
//	}
//
//}



//void _mesort(int* arr, int left, int right, int* tmp)
//{
//	//分离
//	if (left >= right)
//	{
//		return;
//	}
//	int mid = (left + right) / 2;
//	_mesort(arr, left, mid,tmp);
//	_mesort(arr, mid + 1, right,tmp);
//
//	//合并
//	int begin1 = left, end1 = mid;
//	int begin2 = mid + 1, end2 = right;
//
//	int index = begin1;
//	while (begin1 <= end1 && begin2 <= end2)
//	{
//		if (arr[begin1] < arr[begin2])
//		{
//			tmp[index++] = arr[begin1++];
//		}
//		else
//		{
//			tmp[index++] = arr[begin2++];
//		}
//	}
//	while (begin1 <= end1)
//	{
//		tmp[index++] = arr[begin1++];
//	}
//
//	while (begin2 <= end2)
//	{
//		tmp[index++] = arr[begin2++];
//	}
//
//	for (int i = left; i <= right; i++)
//	{
//		arr[i] = tmp[i];
//	}
//
//}
//
//void mesort(int* arr, int n)
//{
//	int* tmp = new int[n];
//
//	_mesort(arr, 0, n - 1, tmp);
//
//
//	delete[] tmp;
//}
//
//


void jssort(int* arr, int n)
{
	//根据最大值和最小值决定数组大小
	int max = arr[0], min = arr[0];
	//循环找最大值和最小值
	for (int i = 1; i < n; i++)
	{
		if (arr[i] > max) 
		{
			max = arr[i];
		}
		if (arr[i] < min)
		{
			min = arr[i];
		}
	}
	//最大值减去最小值 + 1 ，得出数组大小
	int rang = max - min + 1;
	int* count = new int(rang);
	if (count == nullptr)
	{
		perror("fall");
		exit(1);
	}
	//初始化数组中所有数值为0
	memset(count, 0, rang * sizeof(int));


	//统计数组中每个数据出现的次数
	for (int i = 0; i < n; i++)
	{
		count[arr[i] - min]++;
	}

	//index用来遍历count数组
	int index = 0;
	for (int i = 0; i < rang; i++)
	{
		//用count的计数
		while (count[i]--) 
		{
			//i + 最小数，就是arr原来的数值
			arr[index++] = i + min;
		}
	}
}
//冒泡-稳定
//直接-